public class Main {
    public static void main(String[] arg) {
        public static int[] quickSort(int[] arr) {
            if (arr.length <= 1) {
                return arr;
            }
            int pivot = arr[arr.length / 2];
            List<Integer> left = new ArrayList<>();
            List<Integer> middle = new ArrayList<>();
            List<Integer> right = new ArrayList<>();

}       for (int x : arr) {
        if (x < pivot) {
        left.add(x);
        } else if (x == pivot) {
        middle.add(x);
        } else {
        right.add(x);
        }
        }
        int[] leftArray = left.toArray();
        int[] middleArray = middle.toArray();
        int[] rightArray = right.toArray();
        return quickSort(leftArray) + middleArray + quickSort(rightArray);
        }
        }
